package listbyorder.access101_200.test126;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/9 15:28
 */
public class Solution2 {

    // 方法二： 换了一种判断只有一个元素发生变化的方法
    // 指定一个字符串，把可以与当前字符串匹配上的字符串打成一个list，然后dfs
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> ans = new ArrayList<>();
        List<String> path = new ArrayList<>();
        path.add(beginWord);
        dfs(beginWord, endWord, wordList, ans, path);
        return ans;
    }

    int min = Integer.MAX_VALUE;


    private void dfs(String beginWord, String endWord, List<String> wordList, List<List<String>> ans, List<String> path) {
        if (beginWord.equals(endWord)) {
            if (path.size() < min) {
                ans.clear();
                min = path.size();
                ans.add(new ArrayList<>(path));
            } else if (path.size() == min) {
                ans.add(new ArrayList<>(path));
            }
            return;
        }

        if (path.size() >= min) return;

        // 将wordList创成一个集合
        Set<String> dic = new HashSet<>(wordList);
        // 获取当前字符串beginWord所有可能的邻居节点
        ArrayList<String> neighbors = getNear(beginWord, dic);
        for (String neighbor : neighbors) {
            if (path.contains(neighbor)) {
                continue;
            }
            path.add(neighbor);
            dfs(neighbor, endWord, wordList, ans, path);
            path.remove(path.size() - 1);
        }
    }

    private ArrayList<String> getNear(String beginWord, Set<String> dic) {
        ArrayList<String> res = new ArrayList<>();
        char[] chars = beginWord.toCharArray();

        for (char ch = 'a'; ch <= 'z'; ch++) {
            for (int i = 0; i < chars.length; i++) {
                if (chars[i] == ch) {
                    continue;
                }
                char old_char = chars[i];
                chars[i] = ch;
                if (dic.contains(String.valueOf(chars))) {
                    res.add(String.valueOf(chars));
                }
                chars[i] = old_char;   // 再次交换回来
            }
        }
        return res;
    }
}
